#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e7+10;
int n,m,p,inv[MAXN],pri[1000000],fac[MAXN],tot,phi[MAXN];
bool ispri[MAXN];
void cal()
{
	phi[1]=fac[1]=inv[1]=1;
	for(int i=2;i<=MAXN;++i)
	{
		fac[i]=(LL)fac[i-1]*i%p;
		inv[i]=(LL)(p-p/i)*inv[p%i]%p;
		if(!ispri[i])
		{
			pri[++tot]=i;
			phi[i]=(LL)phi[i-1]*(i-1)%p*inv[i%p]%p;
		}
		else phi[i]=phi[i-1];
		for(int j=1;i*pri[j]<=MAXN&&j<=tot;++j)
		{
			ispri[i*pri[j]]=true;
			if(!i%pri[j])break;
		}
	}
	return;
}
int main()
{
	int T;
	scanf("%d%d",&T,&p);
	cal();
	while(T--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",(LL)fac[n]*phi[m]%p);
	}
	return 0;
}
